{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "bso-fs-timeoptim.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Neofly4023/bso-fs/blob/master/bso_fs_timeoptim.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "metadata": {
        "id": "LFFRO2qoAiLd",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Install dependencies\n",
        "This part is in case you run the book in local, because Colab environment already contains most of popular python packages for ML ( like numpy, pandas and sklearn )"
      ]
    },
    {
      "metadata": {
        "id": "pAUATBVpAdJ2",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "!pip install xlsxwriter pandas numpy sklearn"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "qWW9zZvdAM8T",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Import dependencies\n",
        "This par contains all the dependencies that you need to import to run the notebook"
      ]
    },
    {
      "metadata": {
        "id": "mDIDsIGD-Zoq",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "import os, glob, random, copy, sys, time, re, operator\n",
        "from collections import defaultdict\n",
        "from sklearn import metrics\n",
        "from sklearn.model_selection import train_test_split, cross_val_score, KFold, StratifiedKFold, \\\n",
        "ShuffleSplit\n",
        "from sklearn.neighbors import KNeighborsClassifier\n",
        "from sklearn.svm import SVC\n",
        "from sklearn.preprocessing import StandardScaler\n",
        "from oauth2client.client import GoogleCredentials\n",
        "from google.colab import drive\n",
        "import xlsxwriter"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "eumjpGmwA_k2",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Mounting your drive \n",
        "This part is to mount the drive and be able to save results in it"
      ]
    },
    {
      "metadata": {
        "id": "OzO3p0En-duq",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "gdrive_path = '/content/gdrive'\n",
        "drive.mount(gdrive_path)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "YUOiNscrBJdU",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Bee class\n",
        "This class is the implementation of the Bee Swarm Optimization bee"
      ]
    },
    {
      "metadata": {
        "id": "Ru5acK-e-igy",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class Bee :\n",
        "    def __init__(self,id,problem,locIterations,state):\n",
        "        self.id=id\n",
        "        self.data=problem\n",
        "        self.solution = Solution(self.data,state=state)\n",
        "        self.fitness= 0.0\n",
        "        self.rl_return = 0.0\n",
        "        self.locIterations=locIterations\n",
        "        self.action = []\n",
        "    \n",
        "    def localSearch(self):\n",
        "        best=self.fitness\n",
        "        #done=False\n",
        "        lista=[j for j, n in enumerate(self.solution.get_state()) if n == 1]\n",
        "        indice =lista[0]\n",
        "        \n",
        "        for itr in range(self.locIterations):\n",
        "            while(True):\n",
        "                pos = -1\n",
        "                oldFitness = self.fitness\n",
        "                for i in range(len(self.solution.get_state())):\n",
        "                    \n",
        "                    if ((len(lista)==1) and (indice==i) and (i < self.data.nb_attribs-1)):\n",
        "                        i+=1\n",
        "                    self.solution.state[i]= (self.solution.state[i] + 1) % 2\n",
        "                    \n",
        "                    quality = self.solution.get_accuracy(self.solution.get_state())\n",
        "                    if (quality > best):\n",
        "                        pos = i\n",
        "                        best = quality\n",
        "                    self.solution.state[i]= (self.solution.state[i]+1) % 2\n",
        "                    self.fitness = oldFitness \n",
        "                if (pos != -1):\n",
        "                    self.solution.state[pos]= (self.solution.state[pos]+1)%2\n",
        "                    self.fitness = best\n",
        "                else:\n",
        "                    break\n",
        "            for i in range(len(self.solution.get_state())):\n",
        "                oldFitness=self.fitness\n",
        "                if ((len(lista)==1) and (indice==i) and (i < self.data.nb_attribs-1)):\n",
        "                    i+=1\n",
        "                self.solution.state[i]= (self.solution.state[i] + 1) % 2\n",
        "                quality = self.solution.get_accuracy(self.solution.get_state())\n",
        "                if (quality<best):\n",
        "                    self.solution.state[i]= (self.solution.state[i] + 1) % 2\n",
        "                    self.fitness = oldFitness\n",
        "\n",
        "\n",
        "    def ql_localSearch(self,maxIterIndex,flip):\n",
        "      \n",
        "        \"\"\"The reason why we do this is to \n",
        "        tune the exploitation/exploration trade-off \"\"\"\n",
        "        iterations = int(self.locIterations/maxIterIndex) if self.locIterations > maxIterIndex else 1\n",
        "        for itr in range(iterations):\n",
        "       \n",
        "          state = self.solution.get_state()\n",
        "\n",
        "          next_state, action = self.data.ql.step(self.solution)\n",
        "          next_sol = Solution(self.data,state=next_state)\n",
        "          acc_state = self.solution.get_accuracy(state)\n",
        "          acc_new_state = self.solution.get_accuracy(next_state)\n",
        "\n",
        "          if (acc_state < acc_new_state):\n",
        "              reward = acc_new_state\n",
        "          elif (acc_state > acc_new_state):\n",
        "              reward = acc_new_state - acc_state\n",
        "          else :\n",
        "              if (Solution.nbrUn(state) > Solution.nbrUn(next_state) ):\n",
        "                  reward = 1/2 * acc_new_state\n",
        "              else :\n",
        "                  reward = -1/2 * acc_new_state\n",
        "\n",
        "          self.data.ql.learn(self.solution,action,reward,next_sol)\n",
        "          self.rl_return = self.data.ql.get_q_value(self.solution,action)\n",
        "          self.fitness = acc_new_state\n",
        "          self.solution = next_sol\n",
        "          #print(\"This is acc choosed : {0}\".format(acc_new_state))\n",
        "            \n",
        "    def setSolution(self,solution):\n",
        "        self.solution.set_state(solution)\n",
        "        self.fitness = self.solution.get_accuracy(solution)\n",
        "    \n",
        "    @classmethod\n",
        "    def Rand(self, num, start=None, end=None): \n",
        "        res = [] \n",
        "        if (not start) or (not end): \n",
        "          \"\"\"We used 20%/80% (Pareto's law) to initilize the solution\"\"\"\n",
        "          res = np.random.choice([0,1],size=(num,),p=[8./10,2./10]).tolist()\n",
        "        else: \n",
        "          for j in range(num): \n",
        "              res.append(random.randint(start, end))\n",
        "        return res "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "7Q1zHx0KBWNy",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Swarm class\n",
        "This class is the implementation of the Bee Swarm Optimization swarm"
      ]
    },
    {
      "metadata": {
        "id": "UCVpz2Fh-lT-",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class Swarm :\n",
        "    def __init__(self,problem,flip,maxChance,nbrBees,maxIterations,locIterations):\n",
        "        self.data=problem\n",
        "        self.flip=flip\n",
        "        self.maxChance=maxChance\n",
        "        self.nbChance=maxChance\n",
        "        self.nbrBees=nbrBees\n",
        "        self.maxIterations=maxIterations\n",
        "        self.locIterations=locIterations\n",
        "        self.beeList=[]\n",
        "        self.refSolution = Bee(-1,self.data,self.locIterations,Bee.Rand(self.data.nb_attribs))\n",
        "        self.bestSolution = self.refSolution\n",
        "        self.tabou=[]\n",
        "        Solution.solutions.clear()\n",
        "\n",
        "    def searchArea(self):    \n",
        "        i=0\n",
        "        h=0\n",
        "        \n",
        "        self.beeList=[]\n",
        "        while((i<self.nbrBees) and (i < self.flip) ) :\n",
        "            #print (\"First method to generate\")\n",
        "            \n",
        "            solution=self.refSolution.solution.get_state()\n",
        "            k=0\n",
        "            while((self.flip*k+h) < len(solution)):\n",
        "                solution[self.flip*k +h] = ((solution[self.flip*k+h]+1) % 2)\n",
        "                k+=1\n",
        "            newBee=Bee(i,self.data,self.locIterations,solution)\n",
        "            self.beeList.append(newBee)\n",
        "            \n",
        "            i+=1\n",
        "            h=h+1\n",
        "        h=0\n",
        "        \n",
        "        while((i<self.nbrBees) and (i< 2*self.flip )):\n",
        "            #print(\"Second method to generate\")\n",
        "\n",
        "            solution=self.refSolution.solution.get_state()\n",
        "            k=0\n",
        "            while((k<int(len(solution)/self.flip)) and (self.flip*k+h < len(solution))):\n",
        "                solution[int(self.data.nb_attribs/self.flip)*h+k] = ((solution[int(self.data.nb_attribs/self.flip)*h+k]+1)%2)\n",
        "                k+=1\n",
        "            newBee=Bee(i,self.data,self.locIterations,solution)\n",
        "            self.beeList.append(newBee)\n",
        "            \n",
        "            i+=1\n",
        "            h=h+1\n",
        "        while (i<self.nbrBees):\n",
        "            #print(\"Random method to generate\")\n",
        "            solution= self.refSolution.solution.get_state()\n",
        "            indice = random.randint(0,len(solution)-1)\n",
        "            solution[indice]=((solution[indice]+1) % 2)\n",
        "            newBee=Bee(i,self.data,self.locIterations,solution)\n",
        "            self.beeList.append(newBee)\n",
        "            i+=1\n",
        "        for bee in (self.beeList):\n",
        "            lista=[j for j, n in enumerate(bee.solution.get_state()) if n == 1]\n",
        "            if (len(lista)== 0):\n",
        "                bee.setSolution(Bee.Rand(self.data.nb_attribs))\n",
        "                \n",
        "    def selectRefSol(self):\n",
        "      self.beeList.sort(key=lambda Bee: Bee.fitness, reverse=True)\n",
        "      bestQuality=self.beeList[0].fitness\n",
        "      if(bestQuality>self.bestSolution.fitness):\n",
        "          self.bestSolution=self.beeList[0]\n",
        "          self.nbChance=self.maxChance\n",
        "          return self.bestSolution\n",
        "      else:\n",
        "          if(  (len(self.tabou)!=0) and  bestQuality > (self.tabou[len(self.tabou)-1].fitness)):\n",
        "              self.nbChance=self.maxChance\n",
        "              return self.bestBeeQuality()\n",
        "          else:\n",
        "              self.nbChance-=1\n",
        "              if(self.nbChance > 0): \n",
        "                  return self.bestBeeQuality()\n",
        "              else :\n",
        "                  return self.bestBeeDiversity()\n",
        "      \n",
        "    def distanceTabou(self,bee):\n",
        "        distanceMin=self.data.nb_attribs\n",
        "        for i in range(len(self.tabou)):\n",
        "            cpt=0\n",
        "            for j in range(self.data.nb_attribs):\n",
        "                if (bee.solution.state[j] != self.tabou[i].solution.state[j]) :\n",
        "                      cpt +=1\n",
        "            if (cpt<=1) :\n",
        "                return 0\n",
        "            if (cpt < distanceMin) :\n",
        "                distanceMin=cpt\n",
        "        return distanceMin\n",
        "    \n",
        "    def bestBeeQuality(self):\n",
        "        distance = 0\n",
        "        i=0\n",
        "        pos=-1\n",
        "        while(i<self.nbrBees):\n",
        "            max_val=self.beeList[i].fitness\n",
        "            nbUn=Solution.nbrUn(self.beeList[i].solution.get_state())\n",
        "            while((i<self.nbrBees) and (self.beeList[i].solution.get_accuracy(self.beeList[i].solution.get_state()) == max_val)):\n",
        "                distanceTemp=self.distanceTabou(self.beeList[i])\n",
        "                nbUnTemp = Solution.nbrUn(self.beeList[i].solution.get_state())\n",
        "                if(distanceTemp > distance) or ((distanceTemp == distance) and (nbUnTemp < nbUn)):\n",
        "                    if((distanceTemp==distance) and (nbUnTemp<nbUn)):\n",
        "                        print(\"We pick the solution with less features\")\n",
        "                    nbUn=nbUnTemp\n",
        "                    distance=distanceTemp\n",
        "                    pos=i\n",
        "                i+=1\n",
        "            if(pos!=-1) :\n",
        "                return self.beeList[pos]\n",
        "        bee= Bee(-1,self.data,self.locIterations,Bee.Rand(self.data.nb_attribs))\n",
        "        return bee\n",
        "            \n",
        "    def bestBeeDiversity(self):\n",
        "        max_val=0\n",
        "        for i in range(len(self.beeList)):\n",
        "            if (self.distanceTabou(self.beeList[i])> max_val) :\n",
        "                max_val = self.distanceTabou(self.beeList[i])\n",
        "        if (max_val==0):\n",
        "            bee= Bee(-1,self.data,self.locIterations,Bee.Rand(self.data.nb_attribs))\n",
        "            return bee\n",
        "        i=0\n",
        "        while(i<len(self.beeList) and self.distanceTabou(self.beeList[i])!= max_val) :\n",
        "            i+=1\n",
        "        return self.beeList[i]\n",
        "    \n",
        "    def bso(self,typeOfAlgo,flip):\n",
        "        i=1\n",
        "        while(i<=self.maxIterations):\n",
        "            print(\"refSolution is : \", Solution.str_sol(self.refSolution.solution.get_state()))\n",
        "            self.tabou.append(self.refSolution)\n",
        "            print(\"BSO iteration N° : \",i)\n",
        "            \n",
        "            self.searchArea()\n",
        "\n",
        "            # The local search part\n",
        "            \n",
        "            for j in range(self.nbrBees):\n",
        "              if (typeOfAlgo == 0):\n",
        "                self.beeList[j].localSearch()\n",
        "              elif (typeOfAlgo == 1):\n",
        "                for episode in range(self.locIterations):\n",
        "                  self.beeList[j].ql_localSearch(i,flip)\n",
        "                print( \"\\nFitness of bee \" + str(j) + \" is : \" + str(self.beeList[j].fitness))\n",
        "            self.refSolution = self.selectRefSol()\n",
        "            i+=1\n",
        "            \n",
        "        print(\"[BSO parameters used]\\n\")\n",
        "        print(\"Type of algo : {0}\".format(typeOfAlgo))\n",
        "        print(\"Flip : {0}\".format(self.flip))\n",
        "        print(\"MaxChance : {0}\".format(self.maxChance))\n",
        "        print(\"Nbr of Bees : {0}\".format(self.nbrBees))\n",
        "        print(\"Nbr of Max Iterations : {0}\".format(self.maxIterations))\n",
        "        print(\"Nbr of Loc Iterations : {0}\\n\".format(self.locIterations))\n",
        "        print(\"Best solution found : \",self.bestSolution.solution.get_state())\n",
        "        print(\"Number of features used : {0}\".format(Solution.nbrUn(self.bestSolution.solution.get_state())))\n",
        "        print(\"Accuracy : {0:.2f} \".format(self.bestSolution.fitness*100))\n",
        "        print(\"Size of solutions dict : {0}\".format(len(Solution.solutions)))\n",
        "        print(\"Average time to evaluate a solution : {0:.3f}\".format(Solution.get_avg_time())) \n",
        "        print(\"Global optimum : {0}\".format(Solution.get_best_sol()))\n",
        "        if (typeOfAlgo == 1):\n",
        "          print(\"Return (Q-value) : \",self.bestSolution.rl_return)  \n",
        "        return self.bestSolution.fitness*100, Solution.nbrUn(self.bestSolution.solution.get_state())\n",
        "\n",
        "    \n",
        "    def str_sol(self,mlist):\n",
        "        result = ''\n",
        "        for element in mlist:\n",
        "            result += str(element)\n",
        "        return result"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "EbGzO9NBBgZv",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Solution class\n",
        "This class is the implementation of a solution, it contains attributs that a solution could have ( like the subset of featuresor the evaluation, to not train a model with the same subset of features each time ), it could be extensible to other attributs"
      ]
    },
    {
      "metadata": {
        "id": "AZnb2S8X-qBN",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "\n",
        "    solutions = {} \n",
        "    tot_eval_time = 0\n",
        "\n",
        "    def __init__(self,data,state):\n",
        "        self.data = data\n",
        "        self.state = state\n",
        "        self.accuracy = 0\n",
        "        self.solutions[Solution.str_sol(self.state)] = self.accuracy\n",
        "\n",
        "    def get_accuracy(self,state):\n",
        "        if (Solution.str_sol(state) in Solution.solutions):\n",
        "            if (Solution.solutions[Solution.str_sol(state)] == 0) :\n",
        "                self.set_accuracy(state)\n",
        "        else:\n",
        "          self.set_accuracy(state)\n",
        "\n",
        "        return Solution.solutions[Solution.str_sol(state)]\n",
        "\n",
        "    def get_state(self):\n",
        "        return copy.deepcopy(self.state)\n",
        "\n",
        "    def set_accuracy(self,state): \n",
        "        t1 = time.time()\n",
        "        Solution.solutions[Solution.str_sol(state)] = self.data.evaluate(state)\n",
        "        self.accuracy = Solution.solutions[Solution.str_sol(state)]\n",
        "        t2 = time.time()\n",
        "        Solution.tot_eval_time += t2-t1\n",
        "    \n",
        "    def set_state(self,state): \n",
        "        self.state = copy.deepcopy(state)\n",
        "            \n",
        "    @staticmethod\n",
        "    def get_best_sol():\n",
        "        sorted_sols = sorted(Solution.solutions.items(), key=operator.itemgetter(1), reverse=True)\n",
        "        print(\"Best sol after sort : {0}\".format(sorted_sols[0][1]))\n",
        "        return sorted_sols[0][0] ,sorted_sols[0][1]\n",
        "\n",
        "      \n",
        "    @staticmethod\n",
        "    def get_indexes(mlist):\n",
        "        ilist = []\n",
        "        for i in range(len(mlist)):\n",
        "          if mlist[i] == 1:\n",
        "            ilist.append(i)\n",
        "        return ilist\n",
        "      \n",
        "    @staticmethod\n",
        "    def str_sol(mlist):\n",
        "        result = ''\n",
        "        for element in mlist:\n",
        "            result += str(element)\n",
        "        return result\n",
        "\n",
        "    @staticmethod\n",
        "    def list_sol(key):\n",
        "        mlist = [ int(i) for i in key ]\n",
        "        return mlist\n",
        "      \n",
        "    @staticmethod\n",
        "    def nbrUn(state):\n",
        "        return len([i for i, n in enumerate(state) if n == 1])\n",
        "    \n",
        "    @staticmethod\n",
        "    def attributs_to_flip(nb_att):\n",
        "        return list(range(nb_att))\n",
        "    \n",
        "    @staticmethod\n",
        "    def xor(x, y):\n",
        "        return '{1:0{0}b}'.format(len(x), int(Solution.str_sol(x), 2) ^ int(Solution.str_sol(y), 2))\n",
        "    \n",
        "    @staticmethod\n",
        "    def get_avg_time():\n",
        "      return Solution.tot_eval_time/len(Solution.solutions)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "No1rMDEhCEd5",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Reinforcement learning class\n",
        "This class containts the implementation of the different RL algorithms"
      ]
    },
    {
      "metadata": {
        "id": "fYWjrRN6-vP5",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class QLearning:\n",
        "    def __init__(self,nb_atts,actions):\n",
        "        self.actions = actions\n",
        "        self.alpha = 0.1\n",
        "        self.gamma = 0.9\n",
        "        self.epsilon = 0.1\n",
        "        self.q_table = [ {} for i in range(nb_atts) ] \n",
        "\n",
        "    def get_max_q_value(self,solution,actions_vals):\n",
        "        max_val = 0.0\n",
        "        arg_max = 0\n",
        "\n",
        "        for i in actions_vals: # Basic itirative max search from a list of possible actions\n",
        "            state_i = self.get_next_state(solution,i)\n",
        "            state_i_acc = solution.get_accuracy(state_i)\n",
        "            if state_i_acc > max_val: \n",
        "                max_val = self.get_q_value(solution,i) + state_i_acc\n",
        "                arg_max = i\n",
        "\n",
        "        return max_val, arg_max # We return the max q_value and the action that led to it from that state\n",
        "\n",
        "\n",
        "    def get_q_value(self,solution,action):\n",
        "        \n",
        "        state = solution.get_state()\n",
        "        if not Solution.str_sol(state) in self.q_table[Solution.nbrUn(state)]: \n",
        "            self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)] = {}\n",
        "\n",
        "        if not str(action) in self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)]:\n",
        "            # We initilize the q_table with 0\n",
        "            self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)][str(action)] = 0\n",
        "            \n",
        "        return self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)][str(action)]\n",
        "\n",
        "    \n",
        "    def set_q_value(self,solution,action,val):\n",
        "        state = solution.get_state()\n",
        "        self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)][str(action)] = val\n",
        "\n",
        "    \n",
        "    def step(self,solution):\n",
        "        \n",
        "        if np.random.uniform() > self.epsilon :\n",
        "            \n",
        "            action_values = self.actions\n",
        "            max_val = self.get_max_q_value(solution,action_values)[0] # getting the max next q_value\n",
        "            argmax_actions=[self.get_max_q_value(solution,action_values)[1]] # saving the action that maxmizes the reward\n",
        "\n",
        "            # There may be actions that has the same reward, so we add them to the argmax_avtions\n",
        "            for ac in action_values : \n",
        "              ac_state = self.get_next_state(solution,ac)\n",
        "              ac_state_q_val = self.get_q_value(solution,ac) + solution.get_accuracy(ac_state)\n",
        "              \n",
        "              if ( ac_state_q_val >= max_val ):\n",
        "                  argmax_actions.append(ac) \n",
        "                  # We could make the condition \"equal\", because theorically there won't be any bigger q_value\n",
        "            next_action = np.random.choice(argmax_actions) # We choose a random action from eqaul reward actions\n",
        "            next_state = self.get_next_state(solution,next_action)\n",
        "\n",
        "        else : # This is the exploration condition\n",
        "            next_action = np.random.choice(self.actions)\n",
        "            next_state = self.get_next_state(solution,next_action)\n",
        "\n",
        "        if self.epsilon > 0 :\n",
        "            self.epsilon -= 0.0001 \n",
        "        if self.epsilon < 0 :\n",
        "            self.epsilon = 0\n",
        "\n",
        "        return next_state, next_action \n",
        "\n",
        "    def get_next_state(self,solution,action):\n",
        "        next_state = solution.get_state()\n",
        "        next_state[action] = (next_state[action]+1) % 2\n",
        "        if (Solution.nbrUn(next_state) != 0):\n",
        "          return next_state\n",
        "        else:\n",
        "          return solution.get_state()\n",
        "    \n",
        "    def learn(self,current_sol,current_action,reward,next_sol):\n",
        "        next_action = self.get_max_q_value(next_sol,self.actions)[1] # Get the action with the max reward\n",
        "        new_q = reward + self.gamma * self.get_q_value(next_sol,next_action)  #This part will be multiplied by alpha\n",
        "        self.set_q_value(current_sol,current_action,(1 - self.alpha)*self.get_q_value(current_sol,current_action) + self.alpha*new_q) # This is the basic Q-learning formula"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "ozRRchjjCMpp",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Evaluation class\n",
        "This class contains the implementation of evaluation methods and could be extended to other problems than feature selection"
      ]
    },
    {
      "metadata": {
        "id": "1MknP4sm-ywr",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class FsProblem :\n",
        "    def __init__(self,typeOfAlgo,data,qlearn,classifier=KNeighborsClassifier(n_neighbors=1)):\n",
        "        self.data=data\n",
        "        self.nb_attribs = len(self.data.columns)-1 # The number of features is the size of the dataset - the 1 column of labels\n",
        "        self.outPuts=self.data.iloc[:,self.nb_attribs] # We initilize the labels from the last column of the dataset\n",
        "        self.ql = qlearn\n",
        "        self.classifier = classifier\n",
        "        self.typeOfAlgo = typeOfAlgo\n",
        "\n",
        "    def evaluate2(self,solution):\n",
        "        sol_list = self.sol_to_list(solution)\n",
        "        if (len(sol_list) == 0):\n",
        "            return 0\n",
        "         \n",
        "        df = self.data.iloc[:,sol_list]\n",
        "        array=df.values\n",
        "        X = array[:,0:self.nb_attribs]\n",
        "        Y = self.outPuts\n",
        "        train_X, test_X, train_y, test_y = train_test_split(X, Y, \n",
        "                                                    random_state=0,\n",
        "                                                    test_size=0.1\n",
        "                                                    )\n",
        "        self.classifier.fit(train_X,train_y)\n",
        "        predict= self.classifier.predict(test_X) \n",
        "        return metrics.accuracy_score(predict,test_y)\n",
        "\n",
        "\n",
        "    def evaluate(self,solution):\n",
        "        sol_list = self.sol_to_list(solution)\n",
        "        if (len(sol_list) == 0):\n",
        "            return 0\n",
        "        \n",
        "        df = self.data.iloc[:,sol_list] # For this function you need to put the indexes of features you picked  \n",
        "        array=df.values\n",
        "        X = array[:, 0:self.nb_attribs]\n",
        "        Y = self.outPuts\n",
        "        cv = ShuffleSplit(n_splits=10, test_size=0.1, random_state=0) # Cross validation function\n",
        "        results = cross_val_score(self.classifier, X, Y, cv=cv,scoring='accuracy')\n",
        "        #print(\"\\n[Cross validation results]\\n{0}\".format(results))\n",
        "        return results.mean()\n",
        "\n",
        "    def sol_to_list(self,solution):\n",
        "        sol_list=[i for i, n in enumerate(solution) if n == 1]\n",
        "        return sol_list"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "ki1SQkESCdyV",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Data class\n",
        "This class is the one resbonsible for processing and getting the data ready to be trained"
      ]
    },
    {
      "metadata": {
        "id": "ekyU5LcV-12g",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class FSData():\n",
        "\n",
        "    def __init__(self,typeOfAlgo,location,nbr_exec):\n",
        "        \n",
        "        self.typeOfAlgo = typeOfAlgo\n",
        "        self.location = location\n",
        "        self.nb_exec = nbr_exec\n",
        "        self.dataset_name = re.search('[A-Za-z\\-]*.csv',self.location)[0].split('.')[0]\n",
        "        self.df = pd.read_csv(self.location,header=None)\n",
        "        self.ql = QLearning(len(self.df.columns),Solution.attributs_to_flip(len(self.df.columns)-1))\n",
        "        self.fsd = FsProblem(self.typeOfAlgo,self.df,self.ql)\n",
        "        \n",
        "        self.classifier_name = str(type(self.fsd.classifier)).strip('< > \\' class ').split('.')[3]\n",
        "        path = gdrive_path + '/My Drive/Colab Notebooks/results/'+ self.dataset_name\n",
        "        if not os.path.exists(path):\n",
        "          os.makedirs(path + '/logs/')\n",
        "          os.makedirs(path + '/sheets/')\n",
        "        self.instance_name = str(self.typeOfAlgo) + '-' + str(time.strftime(\"%m-%d-%Y_%H-%M-%S_\", time.localtime()) + self.classifier_name)\n",
        "        log_filename = str(path + '/logs/'+ self.instance_name)\n",
        "        if not os.path.exists(path):\n",
        "          os.makedirs(path)\n",
        "        log_file = open(log_filename + '.txt','w+')\n",
        "        sys.stdout = log_file\n",
        "        \n",
        "        print(\"[START] Dataset \" + self.dataset_name + \" description \\n\")\n",
        "        print(\"Shape : \" + str(self.df.shape) + \"\\n\")\n",
        "        #print(self.df.describe())\n",
        "        print(\"\\n[END] Dataset \" + self.dataset_name + \" description\\n\")\n",
        "        print(\"[START] Ressources specifications\\n\")\n",
        "        #!cat /proc/cpuinfo # Think of changing this when using Windows\n",
        "        print(\"[END] Ressources specifications\\n\")\n",
        "\n",
        "        \n",
        "        sheet_filename = str(path + '/sheets/'+ self.instance_name )\n",
        "        self.workbook = xlsxwriter.Workbook(sheet_filename + '.xlsx')\n",
        "        \n",
        "        self.worksheet = self.workbook.add_worksheet(self.classifier_name)\n",
        "        self.worksheet.write(0,0,'Iteration')\n",
        "        self.worksheet.write(0,1,'Accuracy')\n",
        "        self.worksheet.write(0,2,'N_Features')\n",
        "        self.worksheet.write(0,3,'Time')\n",
        "    \n",
        "    \n",
        "\n",
        "    \n",
        "    def run(self,flip,maxChance,nbrBees,maxIterations,locIterations):\n",
        "        total_time = 0\n",
        "        \n",
        "        for itr in range(1,self.nb_exec+1):\n",
        "          print (\"Execution {0}\".format(str(itr)))\n",
        "          self.fsd = FsProblem(self.typeOfAlgo,self.df,self.ql)\n",
        "          swarm = Swarm(self.fsd,flip,maxChance,nbrBees,maxIterations,locIterations)\n",
        "          t1 = time.time()\n",
        "          best = swarm.bso(self.typeOfAlgo,flip)\n",
        "          t2 = time.time()\n",
        "          total_time += t2-t1\n",
        "          print(\"Time elapsed for execution {0} : {1:.2f} s\\n\".format(itr,t2-t1))\n",
        "          self.worksheet.write(itr, 0, itr)\n",
        "          self.worksheet.write(itr, 1, \"{0:.2f}\".format(best[0]))\n",
        "          self.worksheet.write(itr, 2, best[1])\n",
        "          self.worksheet.write(itr, 3, \"{0:.3f}\".format(t2-t1))\n",
        "          \n",
        "        print (\"Total execution time of {0} executions \\nfor dataset \\\"{1}\\\" is {2:.2f} s\".format(self.nb_exec,self.dataset_name,total_time))\n",
        "        self.workbook.close()\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "PbqnYZXyCoG_",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# The main program\n",
        "In the part you can specify the parameters' values.\n",
        "Those parameters are :\n",
        "\n",
        "\n",
        "*   **dataset** : the dataset name ( without **.cvs** extension ), from the list of [datasets](https://github.com/Neofly4023/bso-fs/tree/master/datasets), or you can put your own **.csv** dataset (without header row, and index column)\n",
        "*   **typeOfAlgo** : for now, the value is 0, for the original localsearch algorithm, or 1, for the q-localsearch algorithm\n",
        "*  **nbr_exec** : the number of executions\n",
        "*  **flip** : the flip parameter is used to generate solutions from the searchArea\n",
        "*  **maxChance** : the maxChance parameter is a used for exploitation\n",
        "*  **nbrBees** : the number of Bees used\n",
        "*  **maxIterations** : the number of iterations inside the BSO algorithm, it is possible to not reach it\n",
        "*  **locIterations** : the number of iterations inside the localsearch algorithms (orginal & q-learning)\n",
        "\n",
        "For more details, please check the previous [work](https://link.springer.com/chapter/10.1007%2F978-3-319-19258-1_33), or PM me via : [e-mail](mailto:ea_remache@esi.dz)"
      ]
    },
    {
      "metadata": {
        "id": "GeFvyPenG1FN",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Main program\n",
        "\n",
        "# Prepare the dataset\n",
        "\n",
        "dataset = \"Glass\"\n",
        "data_loc_path = \"https://raw.githubusercontent.com/Neofly4023/bso-fs/master/datasets/\"\n",
        "location = data_loc_path + dataset + \".csv\"\n",
        "\n",
        "# Params init\n",
        "\n",
        "typeOfAlgo = 0\n",
        "nbr_exec = 1\n",
        "flip = 5\n",
        "maxChance = 3\n",
        "nbrBees = 10\n",
        "maxIterations = 2\n",
        "locIterations = 5\n",
        "\n",
        "instance = FSData(typeOfAlgo,location,nbr_exec)\n",
        "instance.run(flip,maxChance,nbrBees,maxIterations,locIterations)"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}